This invention relates to a method and apparatus for hidden surface removal.
In a computer graphics system, an image is displayed on the screen of a cathode-ray-tube (CRT) or other display device. Generally, the electron beam of the CRT is deflected under control of a digital signal having an X (horizontal) component and a Y (vertical) component, so that pixels on a rectangular array of grid points are addressed row-by-row in accordance with a raster pattern. Data representing the image is generated in a host computer and is down-loaded from the host computer to a frame buffer. The frame buffer has memory locations which correspond on a one-to-one basis with the grid points of the CRT display. In the following description, it will be assumed for the sake of clarity that the memory locations of the frame buffer are physically arranged in a rectangular array which corresponds to the array of grid points of the display.
The digital signal that is used to control deflection of the CRT's electron beam is also used to control addressing of the frame buffer, and the color with which the pixel at a grid point is displayed depends on the contents of the corresponding memory location. The frame buffer thus contains a virtual image of the display that is provided by the CRT. The data provided to the frame buffer by the host computer may represent an image composed of colored areas. The process of loading data values into the frame buffer memory to represent a colored area is called tiling. In the following description, references are made in connection with a tiling operation to the tiling of specified grid points and to the tiling of triangles. However, this is intended merely as an abbreviated way of referring to the tiling of the memory locations corresponding to the specified grid points and to the tiling of the memory locations corresponding to the grid points that lie within the triangles.
A triangular surface in three-dimensional space can be defined by a plane equation Z=AX+BY+C and the coordinates of its three vertices. A computer graphics system may be used to depict a three-dimensional object having triangular surfaces by projection of those surfaces into a two-dimensional display plane (Z=0). Each triangular surface forms a triangle or a line when projected into the display plane. The case in which the projection is a line will not be considered further herein. Information defining the triangular surfaces in three-dimensional space is specified to a host computer, which utilizes that information to generate information defining the corresponding display plane triangles. This information is made available by the host computer to a rendering engine, which is used to load shading intensity values into the frame buffer. Generally, the triangular surfaces are treated sequentially by the host computer. In order to provide an accurate depiction, it is necessary to take account of the fact that when a three-dimensional object is examined, surfaces of the object that are on the far side of the object from the viewer cannot be seen, and therefore data representing these surfaces should not be loaded into the frame buffer. In a graphics system, this is accomplished by hidden surface removal. Before loading an intensity value I for a point of a triangular surface (corresponding to a grid point in the display plane) into the frame buffer, a Z value (Znew) representing the distance of that point from the display plane is calculated and is compared with a Z value (Zold) already present in a separate buffer (the Z buffer) for that point. The Z buffer is initially loaded with a Z value for each grid point that represents the greatest distance from the display plane within the range of distance values that can be stored in the Z buffer. If Znew represents a smaller distance than Zold, the intensity value is written into the corresponding memory location of the frame buffer, overwriting any intensity value previously stored at that location, and Znew is written into the corresponding location of the Z buffer, overwriting Zold. Otherwise, the value Zold remains in the Z buffer and the intensity value stored in the frame buffer is unchanged. Hidden surface removal is discussed in Newman and Sproull, "Principles of Interactive Computer Graphics" (McGraw-Hill Book Company, 1979), Second Edition, 369.
The rendering engine of a previously known three-dimensional graphics system receives data representing the coordinates (X, Y) of each vertex of a triangle obtained by projecting a triangular surface into the Z=0 plane and also receives functions that relate Z and I to values of X and Y. The rendering engine generates coordinates of the grid points inside the triangle and values of Z and I for each grid point. The rendering engine communicates with both the frame buffer and the Z buffer. In a first operating cycle, the rendering engine computes the coordinates of a grid point, and on a second operating cycle it computes Znew for that grid point. On the third cycle, Zold for the corresponding memory location is read from the Z buffer, and on the fourth cycle Zold is compared with Znew. If Znew represents a smaller distance than Zold, Znew is written into the Z buffer in the fifth cycle. In the sixth cycle, the value of I is computed for the same grid point, and in the seventh cycle the computed value I is written into the corresponding memory location of the frame buffer. If Znew represents a greater distance than Zold, the rendering engine idles for the fifth, sixth and seventh cycles. Accordingly, seven operating cycles must be performed for each grid point.
U.S. Pat. No. 4,475,104 issued Oct. 2, 1984 discloses a three-dimensional graphics system in which a display processor is used to carry out hidden surface removal.